package sword.chapter8Tree;

/**
 * 序列化和反序列化二叉树
 *
 * 深度优先搜索
 * 序列化      前序遍历，return条件 root==null返回#
 * 反序列化    前序遍历，return条件 str = # 返回null
 *
 * 细节
 * 反序列化时，使用长度为1的数组来记录访问的下标位置。数组是按引用传递
 *
 * @author K
 * @date 2021/12/7 08:49
 */
public class S48Serialize {
    public static String serialize(TreeNode root) {
        if (root == null) {
            return "#";
        }
        String leftStr = serialize(root.left);
        String rightStr = serialize(root.right);

        return String.format("%s,%s,%s", root.val, leftStr, rightStr);
    }

    public static TreeNode deserialize(String data) {
        String[] strs = data.split(",");
        int[] i = new int[]{0};
        return dfs(strs, i);
    }

    private static TreeNode dfs(String[] strs, int[] i) {
        String str = strs[i[0]];
        i[0]++;
        if (str.equals("#")) {
            return null;
        }
        TreeNode node = new TreeNode(Integer.parseInt(str));
        node.left = dfs(strs, i);
        node.right = dfs(strs, i);
        return node;
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        TreeNode node2 = new TreeNode(2);
        TreeNode node3 = new TreeNode(3);
        TreeNode node4 = new TreeNode(4);
        TreeNode node5 = new TreeNode(5);
        TreeNode node6 = new TreeNode(6);
        TreeNode node7 = new TreeNode(7);
        root.left = node2;
        root.right = node3;
        node2.left = node4;
        node2.right = node5;
        node3.left = node6;
        node3.right = node7;

        String result = serialize(root);
        TreeNode node = deserialize(result);
        System.out.println();
    }
}
